package main

import (
	"sort"
)

func main() {
	println(largestSumAfterKNegations([]int{2, -3, -1, 5, -4}, 2))
}
func largestSumAfterKNegations(nums []int, k int) (res int) {
	sort.Ints(nums)
	tmp := 0
	n := 0
	for i := 0; i < k; i++ {
		nums[0] = -nums[0]
		tmp = nums[0]
		n = sort.SearchInts(nums[1:], tmp)
		copy(nums[:n], nums[1:n+1])
		nums[n] = tmp
	}

	for i := 0; i < len(nums); i++ {
		res += nums[i]
	}
	return res
}
